The presently disclosed embodiments are directed toward methods and systems for printing, reproducing or displaying images. More particularly, the teachings disclosed herein are applicable to methods and apparatuses wherein clustered-dot halftoning is implemented.
Digital images may be formatted as contone (continuous tone) images having a wide range of tonal values or may be formatted as coarsely quantized images having a limited number of tonal values, such as two levels for a binary image. Digital halftoning is a process of transforming a contone image to a coarsely quantized image. Digital halftoning is an important step in printing or displaying digital images possessing contone color tones because most printing processes are operating in a binary mode. Examples of such marking processes are offset printing presses, xerography, and ink-jet printing. In these processes, for each color separation of an image, a corresponding colorant spot is either printed or not printed at any specified image location, or pixel. Digital halftoning controls the printing of color dots formed by combinations of colorant spots of a colorant set, where the spatial averaging of the printed colorant dots, such as by the human visual system, provides the illusion of the required continuous tones.
Digital images and the resulting prints are formed of one or more colorant separations, also referred to as “color separations.” A monochrome image is formed of one colorant separation, typically black. Process color images are typically constructed of cyan, magenta, yellow, and black separations. Duotone and tritone images, are formed of two and three separations, respectively. Spot color images have multiple colorant separations, where at least one colorant is positioned spatially nonoverlapping with other colorants. Extended colorant set images typically include the process-color colorant separations plus one or more additional colorant separations such as green, orange, violet, red, blue, white, varnish, light cyan, light magenta, gray, dark yellow, metallics, and so forth. In the present teachings, we will use the terms “color images”, “color dots”, “color spots”, “colorant” and similar language to refer to images and marking systems with any number of colorants. The teachings herein apply particularly to any individual color separation of a digital image and resulting print, where that digital image or print can be composed of one or more separations. With the advent of computers, it is desirable for graphic artists and others to manipulate contone images and print them as halftone images. However, typical computer printers and typesetters are incapable of printing individual halftone dots in an infinite number of sizes. Instead, each halftone dot of a printed picture is in turn comprised of a collection of discrete, smaller “spots” or “pixels”, which are generally the smallest marks a printer or typesetter can make.
FIG. 1 illustrates how one such dot may be made up of individual pixels. A grid 100 is comprised of a set of 100 contiguous pixels, and therefore, is capable of representing 101 shades, or levels, of gray from totally light and white (0% gray level and no pixels darkened) to totally dark and black (100% gray level and all pixels darkened). For every 1% increase in darkness, one pixel in the set will be darkened, or turned on for printing. For example, at 1% gray, a single pixel 1 is darkened. At 2% gray, pixel 2 is darkened as well, so that the dot is comprised of two pixels. At 10% gray, ten pixels 1-10 are darkened. Pixels are either dark and thus printed, or not dark and not printed, and are not individually capable of representing shades of gray.
A common halftone technique is called screening, which compares the required continuous color tone level of each pixel for each color separation with one or more predetermined threshold levels. The predetermined threshold levels are typically defined for halftone cells that are tiled to fill the plane of an image, thereby forming a halftone screen of threshold values. At a given pixel, if the required color tone level is greater than the halftone threshold level for that pixel, a “1” is generated in the halftone output, so that a colorant spot is printed at that specified pixel in the subsequent printing operation. If the required color tone at a given pixel is less than the halftone threshold level for that pixel, a “0” is generated in the halftone output, so that a colorant spot is not printed at that specified pixel in the subsequent printing operation. The output of the screening process is a binary pattern that controls the printing of multiple small spots or pixels that are printed. The printed spots can be grouped or “clustered” to form print structures that are relatively stable for a given printing process. We refer to these clusters as “clustered-dots” or “dots”, and they are regularly spaced as determined by the size, shape, and tiling of the halftone cell. Conventional periodic halftone screens and halftone screen outputs can be considered as two-dimensional repeated patterns, possessing two fundamental spatial frequencies, which are completely defined by the geometry of the halftone screens.
When halftoning using screening, rather than darkening a random pixel in a cell for every increase in gray level, it is preferable for the pixels to be darkened in a specific order pursuant to a dot shape function, also known as a dot function or spot function. The order of darkening pixels in FIG. 1 reflects a dot shape function which attempts to maintain a generally compact shape for the dot as it increases in size to represent increasing gray levels. Topological curves (labeled from 10% to 100% in increments of 10%) generally define the outline of the dot as it increases in gray level. At 10% gray, the darkened pixels substantially conform with the 10% curve, and form a nearly circular dot around the center 110 of the dot shape function. At 20% gray, the darkened pixels form a slightly larger dot which substantially conforms with the 20% curve. At 50% gray, the pixels form a dot which is in substantially the shape of a diamond. The diamond shape in this example is an attempt to control the way in which neighboring dots touch. The gray level of printed dots tends to be printed with a more consistent darkness if the dot touch points are optimized for the given marking process. It is common to optimize the touch points by shaping the dots to touch at corners rather than boundaries of circles or other shapes, but certain marking processes may require other shape optimization, such as straight side touching or curved boundary touching. At 90% gray, nearly all of the pixels are darkened except for 10 pixels 91-100, these pixels being evenly dispersed at the four corners of the dot.
It is often desirable to store the pixels' representation of the dot shape function in memory for later use. To do so, the dot shape function is evaluated at the location of each pixel in the cell, the pixels are rank ordered according to their respective dot shape function values, and a threshold value from 0% to 100% is assigned to each pixel according to its rank. The values are often stored in bit form, such as 0 to 255 for an 8 bit system. Where dot shape function values are identical or nearly identical (within roughly 10%) for multiple pixels in a dot, their order can be determined by any of a number of secondary considerations. For, instance a marking process or imager may mark pixels in a more consistent manner if pixels are preferentially added to a side, such as the lead edge, or trail edge of the dot as it moves through the process or start-of-scan or end-of-scan aide of a dot relative to a laser imager scanning direction. Angular considerations are sometimes used to rank pixels. For instance, to have minimal displacement of the centroid of the dot from gray level to gray level, pixels with nearly identical dot shape function values are sometimes selected by spiraling around the dot in quadrant steps. As another example, printed dot consistency is sometimes achieved by preferentially growing a dot in a vertical or horizontal direction where pixels having nearly identical dot shape function values are ranked to provide more growth in the preferred direction. In some cases, the fill order for pixels of nearly identical dot shape function values could be random, or selected by any of a number of other criteria. In this way, each pixel has an associated “threshold value” in the halftone screen which is equal to the gray level at which that pixel is darkened in the printed image.
Referring to FIG. 2, if a dot which represents a gray level of 75% is desired, the dot is created by darkening every pixel with a threshold value of 75% or less. A 75% gray-level dot is indicated by outline 200. A single collection of pixels with threshold values representing a dot shape function can be referred to as a “halftone cell” or “cell.” As used herein, a cell is a quantized representation of a dot shape function, and for a given cell, the threshold values of the pixels within the cell map the dot shape function.
In this manner, the “digital screen” is created, as an array of cells with pixels having threshold values. Each pixel has a set position and a set threshold value within the cell. Likewise, each cell has a set position within the digital screen. To create a halftone image, a contone image is broken down into an array of pixel-sized samples, and the gray level of each contone sample is stored. Next, each contone sample is compared with the halftone threshold value of the corresponding pixel in the halftone screen, and the pixel is darkened in the subsequent print image if the gray level of the contone sample is greater than the threshold value for that pixel. All the pixels of the digital screen are at set positions with respect to one another, such that a contone sample from the “top-left” of the picture would be compared with a pixel at the “top-left” of the digital screen. In other words, each digital screen pixel has a position which corresponds with and is associated with a position on the original contone picture.
FIG. 3 illustrates a portion of a halftone image 300 represented by dots 310. FIG. 3 was created by comparing an input image having a spatially consistent 5% gray value to a digital screen containing a 3-by-3 array of cells. Each cell contained 100 pixels, and only the pixels with threshold values of 5% or less were darkened and printed. Accordingly, a 3-by-3 array of dots was created, each dot having five pixels. FIG. 4 was created by comparing an input image having a spatially consistent 95% gray value to the same digital screen. All the pixels with gray values of 95% or less were darkened and printed to form a halftone image 400. Although the resulting halftone image 400 is really comprised of nine large dots 410, the naked eye perceives the halftone image as being smaller white dots 420 on a field of black. The white dots are groups of the pixels that are formed from halftone screen values having high thresholds. The white dots can be formed from one or more cells.
Halftoning attempts to render images to printable form while avoiding unwanted visual texture, known as moiré, and tone reproduction irregularities. The two key aspects of halftone screen design are the geometry of periodic dot placement and the shape of the halftone dots. Controlling halftone dot shape has been a lower priority in laser printers because printer pixel resolution, typically measured in rasters per inch referring to the number of smallest printable spots per unit length, has been too low. Consider, for example, the task of controlling dot shape of a 212 cell per inch (cpi) halftone screen used with a printer having a resolution of 600 rasters/inch, where the halftone cell is only two rasters in height. As laser printing resolutions reach 2400 rasters/inch, and greater, controlling halftone dot shape provides a greater impact in improving a printed image.
Hexagonal halftones have been used for process-color printing to avoid moiré that can occur with conventional halftone geometries. In particular, hexagonal dot geometries have been used to reduce moiré between yellow screens and cyan or magenta screens at conventional angles, such as taught by U.S. Pat. No. 5,381,247 for “Method for Reducing 2-Color Moiré in 4-Color Printing” to C. Hains, which is hereby incorporated by reference herein in its entirety. However, this method has not been widely adopted since it can create a tone reproduction irregularity, or “bump”, that occurs as the sides of the hexagonal dots grow toward each other when producing darker gray levels in the halftoned image. It is desirable solve this problem with tone reproduction irregularities when using hexagonal halftones to make better use of their advantages as taught by US Publication No. 2008/0130055 for “Moiré-Free Color Halftone Configuration Employing Common Frequency Vectors” to Wang, et al., US Publication No. 2008/0130054 for “N-Color Printing with Hexagonal Rosettes” to Wang, et al., and U.S. Pat. No. 6,798,539 for “Method for Moiré-Free Color Halftoning Using Non-Orthogonal Cluster Screens” to Wang, et al. which are hereby incorporated by reference herein in their entirety.